package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 *
 *  给定一个数组arr，遍历arr中每一个数，对每一个数左边比他小的数累加，得到和
 *
 *  [7,3,2,  1,6,7]
 *
 *   [0 1 2] [3 4 5]
 *    2,2,3,3
 *
 *
 *   [2,3,7,1,6,7]
 *   [0 1 ,2]  [3 4 ,5]
 *               1,6
 *
 *   [3,7,2,1,6,7]
 *   [0,1] [2]  [3,4] [5]
 *                1
 *
 *   初始状态: [7,3,2,  1,6,7]
 *   比6小的数 1+2+3=6
 *   比7小的数 1+2+3+6=12
 *   最终结果为18
 *
 *   提示: 使用归并排序，算法时间复杂度为O(N)*LogN, //每次递归左边每个数跟右边的数比较，小于则累加
 *
 * @since 2.4.0 2022/2/27 19:00
 */
public class Arr_最小和 {



    static int res = 0;

    public static int getMin(int [] arr){
        split(arr,0,arr.length-1);
        return res;
    }

    public static void split(int [] arr, int i,int j){

        if(i < j){
           int middle = (i+j)/2;
            split(arr,i,middle);
            split(arr,middle+1,j);
            merge(arr,i,middle,middle+1,j);
        }

    }

    public static void merge(int [] arr, int i1, int j1, int i2, int j2){

        int start1 = i1;
        int start2 = i2;
        int [] temp = new int[j2-i1+1];
        int tempIdx = 0;

        //左边每个数跟右边的数比较，小于则累加
        for(int n=i1;n<=j1;n++){
            for(int m=i2;m<=j2;m++){
             if(arr[n] < arr[m]){
                 res+=arr[n];
             }
            }
        }

        while(start1 <= j1 && start2 <= j2){

            if(arr[start1] < arr[start2]){
                temp[tempIdx++] = arr[start1++];
            }else{
                temp[tempIdx++] = arr[start2++];
            }
        }

        while(start1 <= j1){
            temp[tempIdx++] = arr[start1++];
        }

        while(start2 <= j2){
            temp[tempIdx++] = arr[start2++];
        }
        tempIdx = 0;
        for(int n = i1;n<=j2;n++){
            arr[n] = temp[tempIdx++];
        }

    }


    public static void main(String[] args) {

        int [] arr = {7,3,2,1,6,7};
        System.out.println(getMin(arr));
        for(int a : arr){
            System.out.print(a+" ");
        }
    }


}
